//https://leetcode.cn/problems/implement-trie-prefix-tree/?envType=study-plan-v2&envId=top-100-liked
//https://leetcode.cn/problems/number-of-islands/?envType=study-plan-v2&envId=top-100-liked

#include <vector>
#include <stack>
#include <list>
#include <map>
#include <string>
#include <unordered_map>

using namespace std;

class Solution {
public:
    void dfs(vector<vector<char> >& grid,vector<vector<bool>> &visited,int i,int j,int row,int col) {
      if (i>=row || j>=col||i<0||j<0) return;
      if(visited[i][j]) return;
      if(grid[i][j] == '0') return;
      visited[i][j] = true;
      dfs(grid,visited,i-1,j,row,col);
      dfs(grid,visited,i+1,j,row,col);
      dfs(grid,visited,i,j-1,row,col);
      dfs(grid,visited,i,j+1,row,col);
    }
    int numIslands(vector<vector<char>>& grid) {
      // write code here
      int res = 0;
      if(grid.empty()) return res;
      int rows = grid.size();
      int cols = grid[0].size();
      //记录 visited
      std::vector<std::vector<bool>> visited(rows,std::vector<bool>(cols,false));
      for(int i=0;i<rows;++i) {
        for(int j=0;j< cols;++j){
          if(grid[i][j] == '0' || visited [i][j] == true) continue;
          dfs(grid,visited,i,j,rows,cols);
          ++res;
        }
      }
      return res;
        
    }
};